package com.shuzijun.leetcode.editor.cn;
public class ThreeStepsProblemLcci{
    public static void main(String[] args) {
         Solution solution = new ThreeStepsProblemLcci().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public int waysToStep(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        int a = 1;
        int b = 2;
        int c = 4;
        int d = 0;
        for (int i = 4; i <= n; i++) {
            d = ((c+b)%1000000007 + a)%1000000007;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}